package three;
import java.util.*;
public class A047 {




    //前缀和
    //前缀和
    Map<Long,Integer> hash = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        hash.put(0L,1);
        return dfs(root,0L,targetSum);
    }
    public int dfs(TreeNode root, Long key,int sum) { //返回答案的个数
        if(root==null) return 0;
        key += root.val;
        int ret = 0;
        ret += hash.getOrDefault(key-sum,0); //寻找前缀和:假设key=9.sum=8,hash中存在一个1，说明路径存在
        hash.put(key,hash.getOrDefault(key,0)+1);//存入前缀和
        //递归
        ret += dfs(root.left,key,sum);
        ret += dfs(root.right,key,sum);
        //回溯
        hash.put(key,hash.getOrDefault(key,0)-1);//保证是一条路径下的答案
        return ret;
    }

}
